2017ICPC Qindao K 建图网络流

Posted on | In , , ,

题意长的一匹，看博客吧

题目链接

题解

  • 最终其实只有两种可行的旅行方案
  • 方案1.西安-浦东-虹桥-青岛-虹桥-浦东
  • 方案2.西安-虹桥-青岛-浦东
  • md这个链怎么建图啊
  • 仔细分析这两个方案，你会发现考虑虹桥这个点，这次旅行可以看做，虹桥到青岛一次，虹桥到西安一次，浦东到青岛一次。
  • 细致分析可知，青岛和虹桥必须有边，浦东和青岛或者西安有一条边就可行，故浦东和虹桥不需要建边。
  • 考虑到每个点有流量限制，故对每个点拆点
  • S虹桥i连一条容量为INF费用为0的边
  • S和浦东i连一条容量为INF费用为0的边
  • T和青岛i’连一条容量为INF费用为0的边
  • T和西安i’连一条容量为INF费用为0的边
  • 虹桥两个点(i,i’)之间连一条容量为2费用为0的边
  • 青岛两个点(i,i’)之间连一条容量为2费用为0的边
  • 西安两个点(i,i’)之间连一条容量为1费用为0的边
  • 若最后最大流为3，即存在可行方案，最小费用最大流即为答案

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxed=40000+10;
struct E
{
    int from,to,cap,flow,cost;
};
struct MCMF
{
    int n,m,s,t;
    vector<E> edg;
    vector<int> G[maxed];
    int inq[maxed];
    int d[maxed];
    int p[maxed];
    int a[maxed];

    void init(int n)
    {
        this->n=n;
        for(int i=0;i<=n;i++)
            G[i].clear();
        edg.clear();
    }

    void add_(int from,int to,int cap,int cost)
    {
        edg.push_back((E){from,to,cap,0,cost});
        edg.push_back((E){to,from,0,0,-cost});
        m=edg.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BellmanFord(int s,int t,int &flow,int &cost)
    {
        for(int i=0;i<=n;i++)
            d[i]=INF;
        memset(inq,0,sizeof(inq));
        d[s]=0;inq[s]=1;p[s]=0;a[s]=INF;

        queue<int> Q;
        Q.push(s);
        while(!Q.empty()){
            int u=Q.front();
            Q.pop();
            inq[u]=0;
            for(int i=0;i<G[u].size();i++){
                E& e=edg[G[u][i]];
                if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
                    d[e.to]=d[u]+e.cost;
                    p[e.to]=G[u][i];
                    a[e.to]=min(a[u],e.cap-e.flow);
                    if(!inq[e.to]){
                        Q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }
        if(d[t]==INF)
            return false;
        flow+=a[t];
        cost+=d[t]*a[t];
        int u=t;
        while(u!=s){
            edg[p[u]].flow+=a[t];
            edg[p[u]^1].flow-=a[t];
            u=edg[p[u]].from;
        }
        return true;
    }

    int Mincost(int s,int t)
    {
        int flow=0,cost=0;
        while(BellmanFord(s,t,flow,cost));
        if(flow==3)
            return cost;
        return INF;
    }
}mc;
map<string,int> ma;
int n;
int main()
{
    std::ios::sync_with_stdio(false);
    int N;
    cin>>N;
    while(N--){
        ma.clear();
        cin>>n;
        mc.init(4*n+1);
        int cnt=0,a;
        string s1,s2;
        for(int i=1;i<=n;i++){
            cin>>s1>>s2>>a;
            if(!ma.count(s1))
                ma[s1]=++cnt;
            if(!ma.count(s2))
                ma[s2]=++cnt;
            mc.add_(ma[s1]+2*n,ma[s2],INF,a);

            mc.add_(ma[s2]+2*n,ma[s1],INF,a);
        }
        map<string,int>::iterator it;
        for(it=ma.begin();it!=ma.end();it++){
            if(it->first=="Xian"){
                mc.add_(it->second+2*n,4*n+1,1,0);

                mc.add_(it->second,it->second+2*n,1,0);
            }
            else if(it->first=="Qingdao"){
                mc.add_(it->second+2*n,4*n+1,2,0);

                mc.add_(it->second,it->second+2*n,2,0);
            }
            else if(it->first=="Hongqiao"){
                mc.add_(0,it->second,2,0);

                mc.add_(it->second,it->second+2*n,2,0);
            }
            else if(it->first=="Pudong"){
                mc.add_(0,it->second,1,0);

                mc.add_(it->second,it->second+2*n,1,0);
            }
            else{
                mc.add_(it->second,it->second+2*n,1,0);
            }
        }
        int answer=mc.Mincost(0,4*n+1);
        if(answer==INF)
            cout<<-1<<endl;
        else
            cout<<answer<<endl;
    }
    return 0;
}